package find;

//二分查找
public class BinarySearch {

	/*
	 * static void swap(Integer a,Integer b){ if(a>b){ int temp; temp=a; a=b;
	 * b=temp; } }
	 */
	public static void main(String[] args) {
		int[] array = { 2, 3, 5, 6, 9, 10, 15, 35, 44, 51 };
		// findNum(array, 5);
//		findNum2(array, 0, array.length - 1, 34);
//		System.out.println(findNum3(array, 50, 0, array.length - 1));
		System.out.println(findNum4(array, 0, 0, array.length - 1));

	}

	// 普通查找
	public static void findNum(int[] a, int number) {
		for (int i = 0; i < a.length; i++) {
			if (number == a[i]) {
				System.out.println("找到" + number + ",是数组中的第" + (i + 1) + "个元素");
			}
		}
	}

	// 折半查找，也即二分查找
	public static void findNum2(int[] a, int left, int right, int number) {
		//避免bad inptut
		if(left >= a.length){
			return ;
		}
		if (left > right) {
			System.out.println("您输入的已排好序的数组中找不到您输入的数字");
			return;
		}
		// 这里本来应该是(right+left)/2
		// 但是考虑到right+left可能超过范围，不管怎样，这都是必须考虑的，故使用了下面的写法。
		int mid = left + (right - left) / 2;
		if (a[mid] == number) {
			System.out.println("找到" + number + ",是数组中的第" + (mid + 1) + "个元素");
		} else if (a[mid] > number) {
			findNum2(a, left, mid - 1, number);
		} else {
			findNum2(a, mid + 1, right, number);
		}
	}
	//如果存在则返回第一次出现的位置
	public static int findNum3(int[] A, int target, int left, int right) {
		int index = -1;
		if (left >= A.length || left > right) {
			return -1;
		}
		int middle = left + (right - left) / 2;
		if (A[middle] == target) {
			// 注意这里要返回的是第一次出现的次数
			for (int i = middle - 1; i >= 0; i--) {
				if (A[i] == target) {
					middle = i;
				} else {
					return middle;
				}
			}
			return middle;
		} else if (A[middle] < target) {
			index = findNum3(A, target, middle + 1, right);
		} else {
			index = findNum3(A, target, left, middle - 1);
		}
		return index;
	}
	
	//如果不存在，则返回应该插入的位置
	public static int findNum4(int[] A, int target, int left, int right) {
		int index = 0;
		//注意可能超过length - 1，比如比最大的元素还要大
		if (left >= A.length ) {
			return left;
		}
		if(left == right ){
			return A[left] >= target ?  left : left + 1;
		}
		int middle = left + (right - left) / 2;
		if (A[middle] == target) {
			return middle;
		} else if (A[middle] < target) {
			index = findNum4(A, target, middle + 1, right);
		} else {
			index = findNum4(A, target, left, middle - 1);
		}
		return index;
	}
}
